import java.util.*;

//import java.util.ArrayList;
//import java.util.List;
//import java.util.Scanner;
//
//// Press Shift twice to open the Search Everywhere dialog and type `show whitespaces`,
//// then press Enter. You can now see whitespace characters in your code.
//class Person{
//    private String name;
//    private int age;
//
//    public Person(String name, int age) {
//        this.name = name;
//        this.age = age;
//    }
//    public Person()
//    {
//
//    }
//    @Override
//    public String toString() {
//        return "Person[" +
//                "name='" + name +
//                ", age=" + age +
//                ']';
//    }
//
//    public String getName() {
//        return name;
//    }
//
//    public int getAge() {
//        return age;
//    }
//
//    public void setName(String name) {
//        this.name = name;
//    }
//
//    public void setAge(int age) {
//        this.age = age;
//    }
//}
// class Main {
//    public static void main(String[] args) {
//        List<Person> list=new ArrayList<Person>();
//        Scanner sc=new Scanner(System.in);
//        int n=sc.nextInt();
//        for(int i=0;i<n;i++)
//        {
//            String name=sc.next();
//            int age=sc.nextInt();
//            Person tmp=new Person(name,age);
//            list.add(tmp);
//        }
//        String query=sc.next();
//        int pos=-1;
//        for(int i=0;i<list.size();i++)
//        {
//            System.out.println(list.get(i));
//            if(list.get(i).getName().equals(query))
//            {
//                pos=i;
//            }
//        }
//
//    }
//}
//class Student{
//    private int id;
//    private String name;
//    private int score;
//
//    public Student(int id, String name, int score) {
//        this.id = id;
//        this.name = name;
//        this.score = score;
//    }
//
//    public int getId() {
//        return id;
//    }
//
//    public String getName() {
//        return name;
//    }
//
//    public int getScore() {
//        return score;
//    }
//
//    public void setId(int id) {
//        this.id = id;
//    }
//
//    public void setName(String name) {
//        this.name = name;
//    }
//
//    public void setScore(int score) {
//        this.score = score;
//    }
//
//    @Override
//    public String toString() {
//        return "no:"+id+"name:"+name+ "score:"+score;
//    }
//
//    @Override
//    public boolean equals(Object o) {
//        if (this == o) return true;
//        if (o == null || getClass() != o.getClass()) return false;
//        Student student = (Student) o;
//        return id == student.id && score == student.score && Objects.equals(name, student.name);
//    }
//
//    @Override
//    public int hashCode() {
//        return Objects.hash(id);
//    }
//}
// public class Main {
//    public static void main(String[] args) {
//        Map<Integer,Student> map=new HashMap<>();
//        Scanner sc=new Scanner(System.in);
//        int n=sc.nextInt();
//        for(int i=0;i<n;i++)
//        {
//            int id=sc.nextInt();
//            String name=sc.next();
//            int score=sc.nextInt();
//            Student stu=new Student(id,name,score);
//            map.put(id,stu);
//        }
//        int cnt=sc.nextInt();
//        while(cnt-->0)
//        {
//            String op=sc.next();
//            if(op.equals("add"))
//            {
//                int id=sc.nextInt();
//                String name=sc.next();
//                int score=sc.nextInt();
//                Student stu=new Student(id,name,score);
//                map.put(id,stu);
//            }
//            else if(op.equals("delete"))
//            {
//                int id=sc.nextInt();
//                map.remove(id);
//            }
//            else if(op.equals("set"))
//            {
//                int id=sc.nextInt();
//                int score=sc.nextInt();
//                map.get(id).setScore(score);
//            }
//        }
//        Iterator<Integer> it=map.keySet().iterator();
//        while(it.hasNext())
//        {
//            Integer key=it.next();
//            System.out.println(map.get(key).toString());
//        }
//    }
//}
//import java.util.*;
//abstract  class Animal{
//    private String name;
//    private int age;
//
//    public Animal(String name, int age) {
//        this.name=name;
//        this.age=age;
//    }
//
//    public String getName() {
//        return name;
//    }
//
//    public int getAge() {
//        return age;
//    }
//
//    public void setName(String name) {
//        this.name = name;
//    }
//
//    public void setAge(int age) {
//        this.age = age;
//    }
//}
//class Bird extends Animal{
//    public Bird(String name, int age) {
//        super(name,age);
//    }
//    public String getName() {
//        return super.getName();
//    }
//
//    public int getAge() {
//        return super.getAge();
//    }
//    @Override
//    public String toString() {
//        return "Bird[name="+super.getName()+", age="+super.getAge()+"]";
//    }
//}
//
//class Dog extends Animal{
//    private int leg;
//    public Dog(String name, int age,int leg) {
//        super(name,age);
//        this.leg=leg;
//    }
//    public String getName() {
//        return super.getName();
//    }
//
//    public int getAge() {
//        return super.getAge();
//    }
//    public void setLeg(int leg) {
//        this.leg = leg;
//    }
//
//    public int getLeg() {
//        return leg;
//    }
//
//    @Override
//    public String toString() {
//        return "Dog[leg="+leg+", name="+super.getName()+", age="+super.getAge()+"]";
//    }
//}
//public class Main {
//    public static void main(String[] args) {
//        List list=new ArrayList<Animal>();
//        Scanner sc=new Scanner(System.in);
//        int n=sc.nextInt();
//        for(int i=0;i<n;i++)
//        {
//            int tag=sc.nextInt();
//            String name=sc.next();
//            int n1=sc.nextInt();
//
//            if(tag==1)
//            {
//                int n2=sc.nextInt();
//                Dog dog=new Dog(name,n1,n2);
//                list.add(dog);
//            }
//            else{
//                Bird bird=new Bird(name,n1);
//                list.add(bird);
//            }
//
//        }
//        System.out.println(list);
//
//        String query=sc.next();
//        for(int i=0;i< list.size();i++)
//        {
//
//            if(list.get(i) instanceof Bird)
//            {
//                if( ((Bird) list.get(i)).getName().equals(query))
//                {
//
//                    System.out.println("Bird");
//                    System.out.println(((Bird) list.get(i)).toString());
//                    return;
//                }
//
//            }
//            else if(list.get(i) instanceof Dog)
//            {
//                if( ((Dog) list.get(i)).getName().equals(query))
//                {
//
//                    System.out.println("Dog");
//                    System.out.println(((Dog) list.get(i)).toString());
//                    return;
//                }
//
//            }
//        }
//
//        System.out.println("no this one");
//    }
//}

